package 动态规划.组合求和系列;
/**
 * 如果 我 递归 按照  对 集合 中的 每个 元素 进行 要或者 不要
 * 这  2  中可能 进行 构建一颗   2  叉树 
 * 而不是 构建 一棵 多叉树 的  话 
 * 那么  是不是 不需要  进行 最 内层 for 循环的 优化 了
 * 就是 不需要 dp 最终版本的  优化  （即 优化 枚举  行为 ）
 * 
 * 
 * 还是 那 两种 情况 
 * ①：  可重复 选 无重复元素
 * ②： 不可重复 选择 但 有重复 元素
 */
public class 组合求和问题再思考 {
	public static void main(String []args) {
		int candidates []= {6,3,2,4,5};
		int target = 8;
//		System.out.println(process(candidates,target,0));
//		System.out.println(processTwo(candidates,target,0));
//		System.out.println(backTracing(candidates,target,0));
		long t1 = System.currentTimeMillis();
		testOne(candidates,target,1000000);
		long t2 = System.currentTimeMillis();
		System.out.println(t2 - t1);
		long t3 = System.currentTimeMillis();
		testTwo(candidates,target,1000000);
		long t4 = System.currentTimeMillis();
		System.out.println(t4 - t3);
		System.out.println(a);
		System.out.println(b);
		System.out.println(process(candidates,target,0));
		System.out.println(backTracing(candidates,target,0));
		System.out.println(dpOne(candidates,target));
	}
	public static void testOne(int candidates[],int rest,int times) {
		for(int i = 0; i < times ;i++) {
			process(candidates,rest,0);
		}
	}
	
	public static void testTwo(int candidates[],int rest,int times) {
		for(int i = 0; i < times ;i++) {
			backTracing(candidates,rest,0);
		}
	}
	
	
	
	/**将 递归 回溯 转换成  多叉树 的 版本
	 * 
	 */
	static int a;
	public static int backTracing(int nums[],int rest,int index) {
		a++;
		if(rest == 0) {
			return 1;
		}
		if(rest < 0) {
			return 0;
		}
		int ans = 0;
		for(int  i = index ; i < nums.length; i++) {
			if(rest - nums[i] >=0 )
			ans +=backTracing(nums,rest - nums[i],i);
		}
		return ans;
	}
		
	
	static int b;
	public static int process(int nums[],int rest,int index) {
		b++;
		if(rest == 0) {
			return 1;
		}	
		
/**  将递归回溯  转换成 二叉树的  版本
 * 
 *   这 两个 if 的 basecase 的 顺序 是很有   讲究的  
 * 而且 要 按照 这个 顺序的 
 * 为啥 ：
 * 因为 index == nums.length 的  时候 rest 可能 为 0 
 * 那这   就 会出问题  的   最终的 结果 会 少一些 情况 这就是  细节  啊 
 * 
 * 
 * 
 * 
 * 
 * 下面 在解释 一下 :
 * 看到这里的 时候 再去   回想一下  leetcode 417 这个 （太平洋  大西洋  的  问题）
 * 下面 这样 写  可以 减少 一下 内存 栈 的 消耗  或者      会不会            更省时间 一些 呢 (省时间 比较  微薄  的 话  其实 就没有 必要 这样写 对吧   )    ??
 * if(rest - nums[index]>= 0)
		ans += process(nums,rest - nums[index],index + 1);
	如果  再 选择  要   当前元素的 时候 加了       判断   那么 
	在 basecase 的 时候 就不用 判断 了 
	
	
	强烈 建议 写成 
	if(rest - nums[index]>= 0)
		ans += process(nums,rest - nums[index],index + 1);
	这种 效率 高些  并且 内存 消耗 更少 一些 
	为啥  ? : 因为          递 归栈  不是 少一些  嘛 这不就 节约   时间   和 空间 了 ??  
	更重要的 是 优化 成  dp 的 时候 也很好 优化 
	
	即 可以 直接 这样写   
	if(index == nums.length) {
			return 0;
		}
	而不用 这样写 	
	if(index == nums.length || rest < 0) {
			return 0;
		}
 */
		if(index == nums.length || rest < 0) {
			return 0;
		}
		int ans = 0;
//		 要 当前 元素
		if(rest - nums[index] >= 0)
//			ans +=process(nums,rest - nums[index],index);  第一句 代码 赋值的时候写不写  + 都无所谓
		ans =process(nums,rest - nums[index],index);
//		不要当前 元素   就是  跳过 当前 元素   那  rest  就不进行任何操作 呗 
		ans +=process(nums,rest,index + 1);
		
		return ans;
	}
	public static int dpOne(int nums[],int target) {
		int len = nums.length;
		int dp[][]  = new int [len + 1][target + 1];
		for(int index = len -1; index >=0 ;index--) {
			dp[index][0] = 1;
			for(int rest = 1; rest <= target; rest++) {
				if(rest - nums[index] >= 0) {
					dp[index][rest] = dp[index][rest - nums[index]];
				}
				dp[index][rest] += dp[index+1][rest];
			}
		}
		return dp[0][target];
	}
	/**
	 * 像这种 组合 要求去重的 问题 怎么 去重
	 * 这是个问题吧 
	 * （已经解决）
	 */
	public static int processTwo(int nums[],int rest,int index) {
		if(rest == 0) {
			return 1;
		}
		if(index == nums.length) {
			return 0;
		}
		int ans = 0;
//		不要  当前  元素
		ans  = processTwo(nums,rest,index + 1);  
//		要当前  元素 
		if(rest - nums[index]>= 0)
		ans += process(nums,rest - nums[index],index + 1);
//		if(rest - nums[index] >0) {
//			ans += processTwo(nums,rest - nums[index],index + 1);
//		}
	
		return ans;
	}
	
}
